//
// Created by 紫霄 on 2020/4/11.
//

#ifndef LEETCODE_12_H
#define LEETCODE_12_H

#include <string>
#include <vector>
using namespace std;
class Solution {
public:
  bool exist(vector<vector<char>> &board, string word) {
    int row = board.size();
    int col = board[0].size();
    bool k[200][200] = {{0}};
    int wordSize = word.size();
    for (int i = 0; i < row; ++i) {
      for (int j = 0; j < col; ++j) {

        //        for (int mm = 0; mm < row; ++mm) {
        //          for (int nn = 0; nn < col; ++nn) {
        //            k[mm][nn] = false;
        //          }
        //        }
        if (findIt(board, row, col, i, j, word, 0, k)) {
          return true;
        };
      }
    }
    return false;
  }

  bool findIt(vector<vector<char>> &board, int row_sz, int col_sz, int row,
              int col, string word, int num, bool (&k)[200][200]) {
    if (!k[row][col]) {
      k[row][col] = true;
      if (board[row][col] == word[num]) {
        if (num == (word.size() - 1)) {
          return true;
        }
        if ((row - 1) >= 0 && !k[row - 1][col] &&
            findIt(board, row_sz, col_sz, row - 1, col, word, num + 1, k)) {
          return true;
        } else if ((row + 1) < row_sz && !k[row + 1][col] &&
                   findIt(board, row_sz, col_sz, row + 1, col, word, num + 1,
                          k)) {
          return true;
        } else if ((col + 1) < col_sz && !k[row][col + 1] &&
                   findIt(board, row_sz, col_sz, row, col + 1, word, num + 1,
                          k)) {
          return true;
        } else if ((col != 0) && !k[row][col - 1] &&
                   findIt(board, row_sz, col_sz, row, col - 1, word, num + 1,
                          k)) {
          return true;
        } else {
          k[row][col] = false;
          return false;
        }
      }
      k[row][col] = false;
    }
    return false;
  }
};
#endif // LEETCODE_12_H
